package GreedyAlgorithm;

/**
 * 使用能装6个和8个苹果的袋子装苹果，如果使用最少数目的袋子
 * 贪心策略：尽量使用装8个苹果的袋子，剩下的看装6个袋子能不能装，
 * 当剩下的苹果数目大于6和8的最小公倍数24时停止尝试，或者在之前就找到了解决方法
 *
 * @author Liaorun
 */
public class AppleMinBags {

    public static void main(String[] args) {
        System.out.println(minBags(100));
    }

    public static int minBags(int apple) {
        if (apple < 0) {
            return -1;
        }

        if ((apple & 1) != 0) {
            // 最低位为1，是奇数不可能装下
            return -1;
        }

        int bag6 = -1;
        int bag8 = apple / 8;
        // 剩下需要小袋子装的苹果
        int rest = apple - 8 * bag8;

        while (bag8 >= 0 && rest < 24) {
            int restUse6 = minBagBase6(rest);
            if (restUse6 != -1) {
                bag6 = restUse6;
                break;
            }

            // 本次尝试失败，少用一个容量8的袋子
            // 重新计算剩下的苹果数目
            rest = apple - 8 * (--bag8);
        }

        // 是否不可以装下 ？ -1 ：袋子总数量
        return bag6 == -1 ? -1 : bag6 + bag8;
    }

    /**
     * 检查一个数是否可以被6整除
     *
     * @param rest 数
     * @return 商
     */
    private static int minBagBase6(int rest) {
        return rest % 6 == 0 ? (rest / 6) : -1;
    }


    /**
     * 打表法解决装苹果问题
     *
     * @param apple 需要装的苹果数
     * @return
     */
    public static int minBagAwesome(int apple) {
        if ((apple & 1) != 0) {
            return -1;
        }

        if (apple < 18) {
            return apple == 0 ? 0 : (apple == 6 || apple == 8) ? 1 : (apple == 12 || apple == 14 || apple == 16) ? 2 : -1;
        }

        return (apple - 18) / 8 + 3;
    }
}
